package com.future;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Description:
 * ������ˮ̯�ϣ�ÿһ������ˮ���ۼ�Ϊ?5?��Ԫ���˿��Ŷӹ�����Ĳ�Ʒ�������˵� bills ֧����˳��һ�ι���һ����
 * <p>
 * ÿλ�˿�ֻ��һ������ˮ��Ȼ�����㸶 5 ��Ԫ��10 ��Ԫ�� 20 ��Ԫ��������ÿ���˿���ȷ���㣬Ҳ����˵��������ÿλ�˿�����֧�� 5 ��Ԫ��
 * <p>
 * ע�⣬һ��ʼ����ͷû���κ���Ǯ��
 * <p>
 * ����һ���������� bills ������ bills[i] �ǵ� i λ�˿͸����ˡ�������ܸ�ÿλ�˿���ȷ���㣬����?true?�����򷵻� false?��
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺bills = [5,5,5,10,20]
 * �����true
 * ���ͣ�
 * ǰ 3 λ�˿�������ǰ�˳����ȡ 3 �� 5 ��Ԫ�ĳ�Ʊ��
 * �� 4 λ�˿����������ȡһ�� 10 ��Ԫ�ĳ�Ʊ�������� 5 ��Ԫ��
 * �� 5 λ�˿���������һ�һ�� 10 ��Ԫ�ĳ�Ʊ��һ�� 5 ��Ԫ�ĳ�Ʊ��
 * �������пͻ����õ�����ȷ�����㣬����������� true��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/lemonade-change
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/12 14:14
 */
public class Solution_860 {

    public static void main(String[] args) {
        int[] bills = {5, 5, 5, 10, 20};
        bills = new int[]{5, 5, 10, 10, 20};
        bills = new int[]{5, 5, 5, 10, 5, 5, 10, 20, 20, 20};
        System.out.println(lemonadeChange(bills));
    }

    /**
     * ��ֵΪ5��10��20
     * 1����ֵΪ5��ֱ�Ӳ�������Ǯ
     * 2����ֵΪ10������ֵΪ5�����Ƿ����0��������ֱ�ӷ���false
     * 3����ֵΪ20������ֵΪ10�����Ƿ����0���������ٿ���ֵΪ5������
     *
     * @param bills
     * @return
     */
    public static boolean lemonadeChange(int[] bills) {
        if (bills == null || bills.length == 0) {
            return true;
        }
        if (bills[0] != 5) {
            return false;
        }
        int N = bills.length;
        Map<Integer, Integer> moneyMap = new HashMap<>();
        moneyMap.put(5, 1);
        moneyMap.put(10, 0);
        moneyMap.put(20, 0);
        for (int i = 1; i < N; i++) {
            boolean isTen = false;
            int rest = bills[i];
            flag:
            while (rest >= 5) {
                if (rest <= 10 || isTen) {
                    /**
                     * 1��rest=5 ����Ҫ����Ǯ
                     * 2��rest=10 ��Ҫ��5��
                     */
                    if (rest > 5) {
                        /**
                         * 5��Ǯ������
                         */
                        int zhang = moneyMap.get(5);
                        /**
                         * ��Ҫ��5��Ǯ������
                         */
                        int needZhang = (rest - 5) / 5;
                        if (needZhang > zhang) {
                            // ���� ֱ�ӷ���
                            return false;
                        }
                        // ����5��Ǯ������
                        moneyMap.put(5, zhang - needZhang);
                        // �ӵ�map��
                        moneyMap.put(bills[i], moneyMap.get(bills[i]) + 1);
                    } else {
                        // ֱ�Ӽӽ��� ����Ҫ����Ǯ
                        moneyMap.put(5, moneyMap.get(5) + 1);
                    }
                    break;
                } else {
                    /**
                     * ��������ֻ������ֵΪ20��
                     * 1���������ֵΪ10�ģ�������ֵΪ10������Ǯ
                     * 2��û�еĻ�������ֵΪ5���������ն����õ���ֵΪ5��
                     */
                    Integer zhang = moneyMap.get(10);
                    if (zhang == 0) {
                        isTen = true; // �����ֵΪ10�Ĳ����ڣ��´�����rest>10��ֱ����5��Ǯ��ֵ����Ǯ
                        continue flag;
                    }
                    rest = rest - 10;
                    moneyMap.put(10, --zhang);
                    continue flag;
                }
            }
        }
        return true;
    }


    public static int ways_v2(LinkedList<Integer> bills, int aim) {
        return process_v2(bills, 0, aim, new LinkedList<Integer>());
    }

    private static int process_v2(LinkedList<Integer> bills, int index, int rest, LinkedList<Integer> list) {
        if (index == bills.size()) {
            if (rest == 0) {
                System.out.println("��ϣ�" + list);
                for (int i = 0; i < bills.size(); i++) {
                    if (list.get(i) != 0) {
                        bills.remove(i);
                    }
                }
            }
            return rest == 0 ? 1 : 0;
        }
        list.addLast(0);
        // ��ѡ
        int a = process_v2(bills, index + 1, rest, list);
        list.removeLast();
        if (a > 0) {
            return a;
        }
        list.addLast(bills.get(index));
        // ѡ��
        a += process_v2(bills, index + 1, rest - bills.get(index), list);
        if (a > 0) {
            return a;
        }
        list.removeLast();
        return a;
    }


    public static int ways(int[] bills, int aim) {
        return process(bills, 0, aim, new LinkedList<Integer>());
    }

    private static int process(int[] bills, int index, int rest, LinkedList<Integer> list) {
        if (index == bills.length) {
            if (rest == 0) {
                System.out.println("��ϣ�" + list);
            }
            return rest == 0 ? 1 : 0;
        }
        list.addLast(0);
        // ��ѡ
        int a = process(bills, index + 1, rest, list);
        list.removeLast();
        list.addLast(bills[index]);
        // ѡ��
        a += process(bills, index + 1, rest - bills[index], list);
        list.removeLast();
        return a;
    }
}
